{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bulb Switcher"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #brainteaser #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #脑筋急转弯 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bulbSwitch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #灯泡开关"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>初始时有&nbsp;<code>n</code><em> </em>个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。</p>\n",
    "\n",
    "<p>第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 <code>i</code> 轮，你每 <code>i</code> 个灯泡就切换第 <code>i</code> 个灯泡的开关。直到第 <code>n</code> 轮，你只需要切换最后一个灯泡的开关。</p>\n",
    "\n",
    "<p>找出并返回 <code>n</code><em>&nbsp;</em>轮后有多少个亮着的灯泡。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/05/bulb.jpg\" style=\"width: 421px; height: 321px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n =<strong> </strong>3\n",
    "<strong>输出：</strong>1 \n",
    "<strong>解释：</strong>\n",
    "初始时, 灯泡状态 <strong>[关闭, 关闭, 关闭]</strong>.\n",
    "第一轮后, 灯泡状态 <strong>[开启, 开启, 开启]</strong>.\n",
    "第二轮后, 灯泡状态 <strong>[开启, 关闭, 开启]</strong>.\n",
    "第三轮后, 灯泡状态 <strong>[开启, 关闭, 关闭]</strong>. \n",
    "\n",
    "你应该返回 1，因为只有一个灯泡还亮着。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bulb-switcher](https://leetcode.cn/problems/bulb-switcher/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bulb-switcher](https://leetcode.cn/problems/bulb-switcher/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '0', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(n**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def bulbSwitch(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return int(math.sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return int(n ** 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return 0 if n <= 0 else math.floor(math.sqrt(n))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(n ** 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        '''if n==0:\n",
    "            return 0\n",
    "        elif n==1:\n",
    "            return n\n",
    "        res=[1 for i in range(n+1)]\n",
    "        res[0]=0\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,n//i+1):\n",
    "                res[i*j]=res[i*j]^1\n",
    "        return sum(res)'''\n",
    "        return int(n**0.5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(math.sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(math.sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(sqrt(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        result = 1\n",
    "        while(True):\n",
    "            if result * result > n:\n",
    "                break\n",
    "            result+=1\n",
    "        return result - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        # 只有i的平方情况下才是奇数次按，所以是保留的\n",
    "        return int(n**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(n**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if 0<n<=3:\n",
    "            return 1\n",
    "        else:\n",
    "            for k in range(n):\n",
    "                if k**2>n:\n",
    "                    break\n",
    "            dp=[0for i in range(k-1)]\n",
    "            dp[0]=3\n",
    "\n",
    "            for i in range(1,k-1):\n",
    "                dp[i]=dp[i-1]+2*(i+1)+1\n",
    "                if dp[i]>=n:\n",
    "                    return i+1\n",
    "                 \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(math.sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        #只有当k是完全平方数时才会有奇数个约数, 此时k位置的登会亮\n",
    "        #0...n范围内的完全平方数个数：floor(n ^ 0.5)\n",
    "        return int(sqrt(n))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return math.isqrt(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(sqrt(n + 0.5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        e00 = dict()\n",
    "        e0 = e00\n",
    "        zero = 0\n",
    "        remain_on = zero\n",
    "        if 0<= n <=10000:\n",
    "            m = n\n",
    "        else:\n",
    "            m = 0\n",
    "            remain_on = int(math.sqrt(n))\n",
    "        # round 1\n",
    "        for i in range(m):\n",
    "            e1 = {i+1: \"on\"}\n",
    "            e0.update(e1)\n",
    "            remain_on += 1\n",
    "        # print(e0)\n",
    "        # round 2\n",
    "        count = zero\n",
    "        for i in range(len(e0)):\n",
    "            count += 1\n",
    "            if count == 2:\n",
    "                e0[i + 1] = \"off\"\n",
    "                remain_on -= 1\n",
    "                count = 0\n",
    "        # round 3...\n",
    "        for i in range(len(e0)):\n",
    "            i += 1\n",
    "            count = 0\n",
    "            if 3 <= i < len(e0)+1:\n",
    "                for j in range(len(e0)):\n",
    "                    count += 1\n",
    "                    if count == i:\n",
    "                        e0[j+1] = change(e0[j+1])\n",
    "                        remain_on += judge(e0[j+1])\n",
    "                        count = 0\n",
    "            elif i == len(e0)+1:\n",
    "                e0[len(e0) + 1] = change(e0[len(e0) + 1])\n",
    "                remain_on += judge(e0[len(e0) + 1])\n",
    "                # print(e0)\n",
    "\n",
    "        return remain_on\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "def change(str0):\n",
    "    str1 = str0\n",
    "    if str1 == \"on\":\n",
    "        str1 = \"off\"\n",
    "    else:\n",
    "        str1 = \"on\"\n",
    "    return str1\n",
    "\n",
    "\n",
    "def judge(str0):\n",
    "    str2 = str0\n",
    "    if str2 == \"on\":\n",
    "        return 1\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(math.sqrt(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(n ** 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bulbSwitch(self, n: int) -> int:\n",
    "        return int(n**0.5)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
